package Demo2;

public class SingleLinkedList {
    private ListNode head;// 头结点

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }

    }

// 1.  任意位置有顺序插入节点
    public void insert(int x){
        ListNode newNode = new ListNode(x);
//        链表为空 或 新节点值小于头节点的值,直接插入到头部
        if (head == null || head.val >= x){
            newNode.next = head;
            head = newNode;
            return;
        }

//      遍历链表 找到要插入的位置
        ListNode cur = head;

        while(cur.next != null && cur.next.val < x){
            cur = cur.next;
        }

//        插入新节点
        newNode.next = cur.next;
        cur.next = newNode;
    }

//    1 -> 2 -> 3 -> 4
    //       2.  设计一算法`，逆置带头结点的动态链表`
    public ListNode reverseList(ListNode head){
        if (head == null || head.next == null) {
            return head;
        }

        // 递归反转后续链表
        ListNode newHead = reverseList(head.next);

        // 调整当前节点的指针，反转链表方向
        head.next.next = head;
        head.next = null;

        // 返回新的头节点
        return newHead;
    }
    // 调用反转链表函数
    public void reverse() {
        head = reverseList(head);
    }

    /*
    使用 归并排序算法
    将两个递增有序链表合并为一个递减有序链表
    */

    public static SingleLinkedList mergeDescending(SingleLinkedList listA, SingleLinkedList listB) {
        ListNode a = listA.head;
        ListNode b = listB.head;
        ListNode headC = null; // 新链表C的头节点

        while (a != null && b != null) {
            if (a.val <= b.val) {
                ListNode tempA = a.next; //
                a.next = headC; // 插入新链表
                headC = a; //更新 headC 的头节点
                a = tempA;
            } else {
                ListNode tempB = b.next;
                b.next = headC;
                headC = b;
                b = tempB;
            }
        }

//        处理A剩下的元素
        while (a != null) {
            ListNode tempA = a.next;
            a.next = headC;
            headC = a;
            a = tempA;
        }

//        处理B剩下的元素
        while (b != null) {
            ListNode tempB = b.next;
            b.next = headC;
            headC = b;
            b = tempB;
        }

        SingleLinkedList result = new SingleLinkedList();
        result.head = headC;
        return result;
    }


    //    打印链表
    public void printList(){
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val+"  ");
            cur = cur.next;
        }
        System.out.println();
    }

}
